/*************************************************
 * 5、线性表A长度为m，线性表B长度为n，
 * 表A和B中的元素均按递增顺序排列，采用链式存储结构，
 * 表头指针为Ha和Hb，请编写一个算法将Ha和Hb合并到Ha中。
 **************************************************/

#include<stdio.h>
#include<malloc.h>

struct NODE;
typedef struct NODE node;
struct NODE{int data;node* next;};

void print_linkedlist(const node* p){
    p=p->next;
    while(p){printf("%d ",p->data);p = p->next;}
    putchar('\n');
}

void add_value(node* h,int b){
    while(1){
        if(NULL == h->next || h->next->data > b){
            // printf("Should add %d.\n",b);
            node* p = malloc(sizeof(node));
            p->data = b;
            p->next = h->next;
            h->next = p;
            return;
        }
        if(h->next->data==b)return;
        h = h->next;
    }
}


void merge(node* ha,node* hb){
    node *p;
    hb = hb->next;
    while(hb){
        while(1){if(ha->next==NULL)break;if(ha->next->data < hb->data)ha=ha->next;else break;}
        p = ha->next;
        ha->next = hb;
        hb = hb->next;
        ha = ha->next;
        ha->next = p;
    }
}

int main(){
    node head_a;
    node* ha = &head_a;
    ha->next = NULL;

    node head_b;
    node* hb = &head_b;
    hb->next = NULL;

    int m = 10,n=5, i = 0;
    int A[10] = {1,3,5,7,9,2,4,6,8,0};
    int B[5] = {-12,-7,3,8,37};

    for(i=0;i<m;i++)add_value(ha,A[i]);
    for(i=0;i<n;i++)add_value(hb,B[i]);
    printf("List A: ");print_linkedlist(ha);
    printf("List B: ");print_linkedlist(hb);

    merge(ha,hb);
    printf("List A: ");print_linkedlist(ha);

    // clean-up
    node* p;
    ha = ha->next;
    hb = hb->next;
    while(ha){p = ha;ha=ha->next;free(p);}
    return 0;
}

